#pragma once
#include <vector>
#include <string>
#include <cstdlib>
#include <vector>
namespace mystl
{
    template <typename T>
    struct BaseCmp
    {
        virtual bool operator()(const T &x, const T &y) = 0;
    };
    template <class T>
    struct greater : public BaseCmp<T>
    {
        bool operator()(const T &x, const T &y)
        {
            return x > y;
        }
    };
    template <class T>
    struct Less : public BaseCmp<T>
    {
        bool operator()(const T &x, const T &y)
        {
            return x < y;
        }
    };
    template <typename T>
    void quick_sort(std::vector<T> &data, int left, int right, BaseCmp<T> &cmper)
    {
        if (left >= right)
            return;
        // 选取基准位置
        int cmp = data[left];
        int l = left, r = right;
        while (l < r)
        {
            while (l < r && cmper(data[r], cmp))
            {
                --r;
            }
            // 走到这里说明满足 l >= r 或者 data[r]的值已经 <= base了
            if (l < r)
            {
                std::swap(data[r], data[l++]);
            }
            // 说明这趟[base,r]的序列中所有比base小的数全部移动到了base的左边

            // 接下来需要将所有比base大的数移动到右边
            while (l < r && cmper(cmp, data[l]))
            {
                ++l;
            }
            if (l < r)
            {
                std::swap(data[l], data[r--]);
            }
        }
        quick_sort(data, left, l, cmper);
        quick_sort(data, l + 1, right, cmper);
    }

    // 归并排序
    template<typename T>
    void Stable_Sort(std::vector<T> &data, int left, int right,BaseCmp<T> &cmper)
    {
        if (left >= right) return;
        static std::vector<T> help(data.size());

        int mid = (right + left) / 2;
        Stable_Sort(data, left, mid,cmper);
        Stable_Sort(data, mid + 1, right,cmper);

        // 借用辅助数组

        // 将数组左侧的数据先填入辅助数组中
        int l = left, r = mid + 1, cur = left;

        while (l <= mid && r <= right)
        {
            if (cmper(data[l],data[r])) help[cur++] = data[r++];
            else help[cur++] = data[l++];
        }

        while (l <= mid) help[cur++] = data[l++];
        while (r <= right) help[cur++] = data[r++];

        for (int i = left; i <= right; ++i) data[i] = help[i];
    }
}